// 拓扑排序，使用邻接表数据结构
#include "./model/ad-list.h"

/// @brief AOV网排序，输出排序结果
/// @param aov 传入原aov网
void AOVSort(AdList aov)
{
	// 初始化一个栈用于存放入度为0的顶点下标
	// 分别表示遍历下标、每次出栈元素、已排序顶点个数、栈顶指针和栈
	int i, temp, count = 0, top = 0, stack[aov->vertexNum];
	// 先把入度为0的点入栈
	for (i = 0; i < aov->vertexNum; i++)
	{
		if (aov->vertexs[i].in == 0)
		{
			stack[top++] = i;
		}
	}
	// 接下来把入度为0的点出栈并排序输出，然后将它们所有邻接点的入度-1，并继续把新的入度为0的点入栈
	EdgeNode *pointer;
	while (top != 0)
	{
		// 出栈并排序
		temp = stack[--top];
		printf("%c -> ", aov->vertexs[temp].data);
		count++;
		// 把这个已排序的点所有的邻接点的入度-1（删除这个点）
		for (pointer = aov->vertexs[temp].firstEdge; pointer != NULL; pointer = pointer->next)
		{
			aov->vertexs[pointer->adjvex].in--;
			// 如果这个点入度为0了则入栈
			if (aov->vertexs[pointer->adjvex].in == 0)
			{
				stack[top++] = pointer->adjvex;
			}
		}
	}
	printf("^\n");
	// 若已排序的点个数小于顶点数，说明存在环，错误
	if (count < aov->vertexNum)
	{
		printf("图中存在环！排序错误！\n");
	}
}

int main()
{
	AdList list = createAdList();
	char c;
	for (c = 'a'; c <= 'g'; c++)
	{
		adListInsertVex(list, c);
	}
	adListInsertArc(list, 0, 1, 0);
	adListInsertArc(list, 0, 3, 0);
	adListInsertArc(list, 1, 3, 0);
	adListInsertArc(list, 1, 2, 0);
	adListInsertArc(list, 1, 4, 0);
	adListInsertArc(list, 3, 5, 0);
	adListInsertArc(list, 3, 6, 0);
	adListInsertArc(list, 2, 5, 0);
	adListInsertArc(list, 4, 5, 0);
	adListInsertArc(list, 4, 6, 0);
	AOVSort(list);
	return 0;
}